#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define LIST_INT_SIZE 100
#define LIST_INCREATMENT 10

typedef int Status;
typedef int ElemType;

typedef struct
{
    ElemType *elem;
    int length;
    int listsize;
} Sqlist;

// 算法2.3
Status InitList_Sq(Sqlist *L) // 初始化线性表
{
    // 构造一个线性表(对线性表初始化)
    L->elem = (ElemType *)malloc(LIST_INT_SIZE * sizeof(ElemType)); // 相当于使用分配地址的方式创建一个数组
    if (!L->elem)                                                   // 如果分配失败就会返回空指针NULL(0)
    {
        return OVERFLOW; // 内存分配失败
    }
    L->length = 0;               // 设置线性表总长度为0
    L->listsize = LIST_INT_SIZE; // 设置线性表最大长度
    return OK;
}

// 算法2.4
Status ListInsert_Sq(Sqlist *L, int i, ElemType e) // 对线性表进行插入
{
    if (i < 1 || i > L->length + 1) // 检查插入的位置，如果大于线性表长度或者小于1返回ERROR
    {
        return ERROR;
    }

    if (L->length == L->listsize) // 如果当前长度超出了线性表最大长度，进行扩充LIST_INCREATMENT个数据大小
    {
        ElemType *newbase = (ElemType *)realloc(L->elem, (L->listsize + LIST_INCREATMENT) * sizeof(ElemType));
        if (!newbase) // 分配失败
        {
            return ERROR;
        }
        L->elem = newbase;               // 更新重新分配的地址
        L->listsize += LIST_INCREATMENT; // 更新线性表的最大地址
    }

    ElemType *q = &(L->elem[i - 1]);                           // 记录下插入位置的数据的值
    for (ElemType *p = &(L->elem[L->length - 1]); p >= q; --p) // 记录下最后位置数据的值[数组下标从零开始所以需要-1]，方便向后移动
    {
        *(p + 1) = *p; // p指针不断后移,知道与q指针重合,在此之前p总是会把当前地址的值赋给邻近的下一个地址，从而实现数据后移
    }
    *q = e;      // 返回e，e是插入的值
    ++L->length; // 线性表长度加一
    return OK;
}

// 算法2.5
Status ListDelete_Sq(Sqlist *L, int i, ElemType *e) // 删除线性表中第i个元素,使用e返回这个元素的值
{
    if (i < 1 || i > L->length)
    {
        return ERROR; // 给定删除的位置非法
    }
    ElemType *q = &(L->elem[L->length - 1]); // 取得线性表最后位置的地址
    ElemType *p = &L->elem[i - 1];           // 取得删除位置的地址
    *e = *p;                                 // 返回删除的元素值

    for (; p <= q; ++p) // p是删除位置的地址 ,p没等于q的位置之前一直循环
    {
        *p = *(p + 1); // p位置上原有的值被它后面的值覆盖,实现删除操作
    }
    L->length--; // 线性表长度减一
    return OK;
}

// 算法2.6
Status LocateElement_Sq(Sqlist *L, ElemType e, int (*compare)(ElemType, ElemType)) // 寻找第一个满足compare函数的值,并且返回其位置
{
    int i = 1; // 初始下标
    ElemType *p = L->elem;
    while (i <= L->length && !(*compare)(*p++, e))
    {
        i++; // 没找到满足的就计数器位置加一
    }
    if (i <= L->length)
    {
        return i;
    }
    return 0;
}
int compare(ElemType i, ElemType e) // compare函数只比较相等,可以根据需要更改
{
    if (i == e)
        return TRUE;
    else
        return FALSE;
}

Status MergeList_Sq(Sqlist *L1, Sqlist *L2, Sqlist *L3) // 非递减顺序合并L1,L2到L3依旧是非递减
{
    // 对L3重新分配空间
    L3->length = L1->length + L2->length;
    ElemType *newbase = (ElemType *)realloc(L3->elem, (L1->listsize + L2->listsize) * sizeof(ElemType));
    if (!newbase) // 内存重新分配失败
    {
        return ERROR;
    }
    L3->elem = newbase;                         // 替换原有的elem地址
    L3->listsize = L1->listsize + L2->listsize; // 替换原有的listsize
    int i = 0;                                  // 记录L3->elem的下标
    ElemType *l1 = L1->elem;                    // l1 和 l2都是elem的首地址,即elem[0]的地址
    ElemType *l2 = L2->elem;
    while (l1 <= &L1->elem[L1->length - 1] && l2 <= &L2->elem[L2->length - 1]) // 归并排序,不多解释
    {
        if (*l1 <= *l2)
        {
            L3->elem[i] = *l1;
            l1++;
            i++;
        }
        else
        {
            L3->elem[i] = *l2;
            l2++;
            i++;
        }
    }
    while (l1 <= &L1->elem[L1->length - 1])
    {
        L3->elem[i] = *l1;
        l1++;
        i++;
    }
    while (l2 <= &L2->elem[L1->length - 1])
    {
        L3->elem[i] = *l2;
        l2++;
        i++;
    }
    return OK;
}

int main()
{
    Sqlist *list = (Sqlist *)malloc(sizeof(Sqlist)); // 建立一个Sqlist结构体

    //------------算法2.3(初始化函数)的调用-------------
    InitList_Sq(list); // 初始化线性表

    //------------算法2.4(插入函数)的调用-------------
    printf("进行插入操作,使得list的值为:\n");
    for (ElemType i = 1; i < 10; ++i) // 使用尾插法构造一个1-9的线性表
    {
        ListInsert_Sq(list, i, i); // ListInsert_Sq(Sqlist *L, int i, ElemType e) 其中i是插入的位置,要求在1开始
    }

    for (int i = 1; i <= list->length; ++i) // 输出线性表的值
    {
        printf("%d ", list->elem[i - 1]);
    }
    printf("\n\n");

    //------------算法2.6(比较函数)的调用-------------
    ElemType e1 = 7;
    int loc = LocateElement_Sq(list, e1, compare);
    printf("e1=%d的位置在%d号\n\n", e1, loc);

    //------------算法2.7(合并两个非递减序列)-----------
    Sqlist *list2 = (Sqlist *)malloc(sizeof(Sqlist)); // 首先再创建一个顺序表
    InitList_Sq(list2);                               // 初始化
    for (ElemType i = 1; i < 10; i++)
    {
        ListInsert_Sq(list2, i, i + 1); // 在第i个位置插入第i个值
    }
    // 输出list2
    printf("输出list2的值:\n");
    for (int i = 1; i <= list2->length; ++i)
    {
        printf("%d ", list2->elem[i - 1]);
    }
    printf("\n\n");
    // 一个合并后的链表list3
    Sqlist *list3 = (Sqlist *)malloc(sizeof(Sqlist)); // 首先再创建一个顺序表
    InitList_Sq(list3);                               // 初始化
    // 合并函数
    MergeList_Sq(list, list2, list3);
    // 输出list3
    printf("输出list3的值:\n");
    for (int i = 1; i <= list3->length; ++i)
    {
        printf("%d ", list3->elem[i - 1]);
    }
    printf("\n");

    //------------算法2.5(删除函数)的调用-------------
    printf("\n进行删除操作:\n");
    ElemType *e = (ElemType *)malloc(sizeof(ElemType)); // 必须为指针分配空间,否则报错
    for (ElemType i = 1; i <= list->length;)            // 不能写++i否则变成了每隔一个数删除一个数
    {
        ListDelete_Sq(list, i, e); // 传入指针
        printf("%d ", *e);         // 每次输出删除的值
    }
    free(e);
    free(list->elem); // 释放elem的空间
    free(list2->elem);
    free(list3->elem);
    free(list); // 释放list空间
    free(list2);
    free(list3);
    return 0;
}
